1. Field of the Invention
The present invention relates to digital signal processing. More particularly, the present invention relates to a novel and improved method and apparatus for performing fast Hadamard transformations.
II. Description of the Related Art
Waveform coding procedures transform a waveform set into an improved waveform set. The improved waveform set can then be used to provide improved probability of bit error PB compared to the original set upon communication. In the improved waveform set the signals are as unlike as possible. Another way of viewing this is to render the cross-correlation between any two waveforms i and j (denoted z.sub.ij)as small as possible.
The cross correlation (z.sub.ij) is defined as: ##EQU1## where s.sub.i (t) and s.sub.j (t) are two waveform functions. In a waveform set comprised of bipolar pulses (+1,-1), the definition of the cross-correlation (z.sub.ij) can be simplified to: ##EQU2##
The smallest possible value of the cross-correlation occurs when the signals are anticorrelated (z.sub.ij =-i); however, this can only be achieved when the number of waveforms in the set are two and the waveforms are antipodal. In general, the best achievable waveform set has all the cross-correction values equal to zero. The set is then said to be orthogonal. The most popular waveform codes used for communication purposes are orthogonal codes.
One method by which a data set can be transformed into an orthogonal data set is by means of a Hadamard transformation. A Hadamard transformation is characterized by a Hadamard matrix, in which each row of the Hadamard matrix is orthogonal to every other row of the matrix, that is in accordance with equation 2, the number of agreements equals the number of disagreements for each pair of rows. Each row of the Hadamard matrix can be referred to as a Walsh sequence.
A Hadamard matrix of order n can be defined recursively as follows: ##EQU3## where H.sub.1 is defined as: EQU H.sub.1 =[1] (4)
and H.sub.i =-H.sub.i.
Thus, ##EQU4##
Similarly, by application of equation 3, H.sub.4 is found to be: ##EQU5## and H.sub.8 is found to be: ##EQU6##
Fast algorithms have been developed to increase the efficiency of in the performance of Hadamard transformations. These implementations exploit the fact that Hadamard matrices are real, symmetric and row-wise orthogonal. Since the Hadamard matrices contain only +1 values, no multiplications are required in the transform calculations. Moreover the number of additions and subtractions required can be reduced from n.sup.2 to n.multidot.log.sub.2 n, due to the fact that a Hadamard matrix of order n (H.sub.n) can be written as a product of n sparse matrices, that is, EQU H.sub.n =H.sub.n log.sbsp.2.sup.(n) ( 8)
where ##EQU7## Noting that the top n/2 rows and the bottom n/2 rows contain only two nonzero terms per row, the transformation EQU v=H.sub.n.sup.log.sbsp.2.sup.(n) =H.sub.n .multidot.H.sub.n . . . H.sub.n .multidot.u (10)
can be accomplished by operating H.sub.n log.sub.2 n times on u. Due to the structure of H.sub.n only n additions and subtractions are required each time H.sub.n operates on a vector, giving a total of n.multidot.log2(n) additions and subtractions.
The problem associated in the implementation of the fast Hadamard transformation described above is the burden on memory resources. In addition, the method described above does not lend itself to serial processing. Accordingly, there is a need for an improved method and apparatus for performing fast Hadamard transforms that lessen the burden on memory resources and lends itself to serial processing. Such a method is the subject of the present invention.